A system where computers are distributed (distributed system) needs destination information of a server, which is a communication destination (e.g., internet protocol (IP) address etc.). Types of methods of managing destinations in distributed systems are, for instance, a central management type, and a peer-to-peer (P2P) type. In the central management type management method, first, a client accesses a dedicated server that manages destinations, and identifies a target server as a destination from the dedicated server. In contrast, in the P2P type management method, each server in a distributed system manages destination information for the other servers (all the servers have functions of management servers).
In a P2P type distributed system, it is preferred to determine a server to which data is to be assigned, by means of calculation, in order to make relationship between servers loose. For this type, a distributed hash table (DHT) is often used. According to the distributed hash table, nodes are mapped into a hash space, which is a set of hash values determined by a prescribed hash function, thereby constructing an overlay network. The method of determining a server as a destination using DHT assigns a key to data, and hashes the key to thereby determine a server to which the data is assigned. It is anticipated that use of DHT allows the distribution of data to servers to be uniform in terms of probability to make loads be distributed. In particular, a hashing method referred to as consistent hashing (CH) has a strong flexibility in adding and deleting servers on a network. Accordingly, this method is applied to fields of distributed data storage systems and distributed cache systems.
For instance, a technology pertaining to distributed systems using DHT is as follows.
A first technology is an information communication system that reduces loads on a node device that transmits information when transmitting the information to a plurality of node devices. The information communication system is formed by participation of the node devices connected to each other via communication paths. In the information communication system, a certain node device X determines representative node devices included in respective groups which are multiple (four) groups and into which the node devices are classified according to a prescribed rule (e.g., DHT). The node device X transmits main information to the determined node devices A, B and C. When the main information received from another node device is destined to the group including the own node device, the node device X transmits the main information received in an analogous manner to the node device as the representative of the group to which the own node device belongs.
A second technology is the following information search method. The information search method holds service information that includes information representing the location, content and the like of information provided by a terminal device that is a service provider, and information for using this information; this method is applied to an information search system that includes communication devices classified into groups on the basis of prescribed conditions. The information search method includes an attribute information acquisition step, a first search step, a request transferring step, and a second search step. The attribute information acquisition step acquires attribute information for identifying service information included in an information search request that requests search of service information. The first search step searches for a group to which a communication device holding target service information belongs on the basis of the attribute information acquired by the attribute information acquisition step. The request transferring step transfers the information search request to the representative communication device of the group which is the result of the first search step. When the own device is the representative communication device, the second search step receives the information search request transferred by the request transferring step and searches for the target service information in the own group.
Systems such as for online stock transaction needs to quickly process enormous requests. Furthermore, in these days, it is difficult to predict the growth in the amount of requests for online transactions. Accordingly, the systems need to have a mechanism for allowing the processing capacity to be flexibly expanded. In order to meet the demand, a distributed processing system that is dynamically expanded is preferable.
The central management type distributed system has a significantly simple structure, and reaches a target server at two communications. However, a management server may become a single fault point, which affects the entire system in case of occurrence of an abnormality. This system also has a drawback in that query communications may easily become a bottleneck in the case where the number of servers significantly increases.
The P2P type distributed system has an advantage of fault-tolerance even in case where some of servers have failed. This system is often adopted as a large-scale distributed system from which availability is needed. In the case of constructing a DHT type overlay network, load distribution is also expected. That is, the drawback of the central management type is solved.
Note that the techniques disclosed in the following documents are also known.    Patent Document 1: Japanese Laid-Open Patent Publication No. 2007-053662    Patent Document 2: Japanese Patent Laid-Open Publication No. 2007-156700    Non-Patent Document 1: Luiz R. Monnerat and Claudio L. Amorim, “D1HT: A Distributed One Hop Hash Table Extended Version”